With rapidly-advancing computer, telecommunication, and digital imaging technologies, there is an astronomical amount of image data for a wide range of applications such as education, entertainment, medical imaging, space exploration, electronic publishing, visual arts, etc. This rapid growth of image data puts punishing burdens on computer storage and visual communication bandwidth. Thus image compression becomes a pressing technical challenge in visual communications and computing, without which it will be difficult to build, deploy, and use cost-effective multimedia information systems.
Lossless compression is a form of compression where an image can be reconstructed without any loss of information. Lossless image compression is required by medical imaging, satellite/aerial imaging, image archiving, preservation of precious art work and documents, the press, or any applications demanding ultra high image fidelity. Furthermore, lossless image coding is the necessary last step of many lossy image compression systems, such as lossless compression of codeword indices in vector quantization (VQ), and lossless compression of transform coefficients in Discrete Cosine Transform (DCT) and wavelet/subband-based coding.
There exists a large body of literature on lossless image compression algorithms and systems, such as the IBM Q-coder, and JPEG lossless coder. Among notable patents and publications are the US patents and research publications listed below:
U.S. Pat. No. 4,463,342 1984 IBM. PA0 U.S. Pat. No. 4,749,983 07/1988 Langdon. PA0 U.S. Pat. No. 4,969,204 11/1989 Melnychuck et al. PA0 U.S. Pat. No. 5,050,230 09/1990 Jones et al. PA0 Universal Modeling and Coding--J. Rissanen and G. Langdon, 1981, IEEE, vol. IT-27. PA0 A Universal Data Compression System--J. Rissanen, 1983, IEEE, vol. IT-29. PA0 Parameter Reduction and Context Selection for Compression of the Gray-Scale Images--S. Todd, G. Langdon, and J. Rissanen, 1985, IBM J. Res. & Develop., vol. 29. PA0 Comparing the Lossless Image Compression Standards and Universal Context Modelling--R. Arps, M. Weinberger, T. Truong, and J. Rissanen, Proc. of the Picture coding Symposium, Sacramento, September 1994. PA0 On the JPEG Model for Lossless Image Compression--G. Langdon, A. Gulati, and E. Seiler, Proc. of 1992 Data Compression Conf. PA0 New Methods for lossless Image Compression Using Arithmetic Coding--P. Howard and J. Vitter, 1992, Info. Proc. & Manag., vol. 28.
The currently achievable lossless compression ratio is still modest, being typically from 1.5:1 to 2.5:1. For instance, in contrast to the success of JPEG's lossy compression standard, the current JPEG's lossless compression standard has sufficiently poor coding efficiency that it is seldom used in practice.
In 1994, ISO and JPEG solicited for proposals for the next international standard for lossless image compression. The present invention is a result of the inventors' response to the ISO solicitation. The lead inventor Xiaolin Wu, developed a context-based, adaptive, lossless image coding and decoding technique (herein CALIC). Among nine proposals that were submitted to ISO for its initial evaluation as candidates for the lossless image compression standard in 1995, the present CALIC system ranked first according to a criterion that accounts for both coding efficiency and algorithm simplicity.
EP A 0 613 290 entitled METHOD AND APPARATUS FOR BINARY IMAGE DATA COMPRESSION published on Aug. 31, 1994 describes a method and apparatus for lossless compression of binary images only. The abstract and specification of EP A 0 613 290 mention that the method and apparatus are applicable to "photographs" and "mixed binary images". However, it is apparent that the photographs referred to are digitally half-toned photographs and not true continuous toned images. The method and apparatus of EP A 0 613 290 only encode binary image data and d o not provide for compression of continuous tone images, graphics, or mixtures of binary images with continuous tone images, and graphics.
EP A 0 547 528 entitled METHOD AND ASSOCIATED APPARATUS FOR ENCODING BIT PLANES published on Jun. 23, 1993 describes a scheme for lossless image compression by bit-plane encoding. Bit plane encoding has significant known disadvantages.
P. E. Tischer et al. Context-based Lossless Image Compression 8199 The Computer Journal vol. 36 no. 1 pp. 68-77 (1993) provides a general academic treatment of the subject of context based lossless image compression.
Known prior art on lossless compression of continuous-tone images is based on the principle of predictive coding. An image is traversed, and pixels are encoded in a fixed order, typically in raster scan sequence. Previously encoded pixels that are known to both the encoder and the decoder are used to predict the upcoming pixels. The prediction errors rather than the pixels themselves are entropy encoded by Huffman or like arithmetic coding. The original image is reconstructed by adding the error term back to the prediction value. The predictive coding works because the histogram of the errors is much more concentrated (heavily biased toward 0) than the histogram of the pixel values, resulting in a significantly smaller zero-order entropy for the former than for the latter. Among numerous prediction schemes in the literature, the simplest type is a fixed linear predictor such as those used under the current lossless JPEG standard.
A linear predictor can be optimized on an image-by-image or even block-by-block basis via linear regression. However, such an optimization is expensive and brings only modest improvement in coding efficiency. Moreover the performance of linear predictors is not robust in the areas of edges. Adaptive, non-linear predictor can adjust parameters according to the local edge strengths and orientations, if edges exist. The adjustment of predictor parameters can be made very efficient since it is based on local information.
Historically, lossless image compression inherited the theoretical framework and methodology of text compression. Statistical modeling of the source being compressed plays a central role in any data compression systems. Suppose that we encode a finite source x.sub.1,x.sub.2, . . . ,x.sub.n sequentially. The optimal code length of the sequence in bits is then ##EQU1## given the assignments of conditional probabilities. Arithmetic coding can approach this code length of the source. The challenge is to assign the conditional probabilities p(x.sub.{i+1} .vertline.x.sub.i, . . . ,x.sub.1) to maximize the product given above, hence minimize the code length. The achievable compression is governed by a scheme, or a model, that can assign high conditional probability distributions p(x.sub.{i+1} .vertline.x.sub.i, . . . ,x.sub.1) to the given sequence.
Fitting a given source well with statistical models is a difficult and computationally very expensive task. Context modeling of continuous-tone images is made even more difficult by the large alphabet size (.gtoreq.256) of grey-scale images. Context modeling of the source symbols (pixel values) would lead to an unwieldily large number of possible model states (contexts). This is more than a problem of high time and space complexities for modeling. If the number of model parameters is too large with respect to the image resolution, there will be insufficient samples to obtain good estimates of conditional probabilities on the model states, leading to poor coding efficiency. This is known as a "context dilution problem." This problem was theoretically formulated by Rissanen in the framework of stochastic complexity as the "model cost." Rissanen's work proves that the high complexity of a model can reduce coding efficiency, as observed by many data compression practitioners. What is needed are innovative algorithmic techniques to reduce the model complexity for improving both coding and computational efficiency.